1. Field of the Invention
The present invention relates to a system and method for evaluating one or more functions of one or more variables.
2. Description of the Related Art
In an article entitled xe2x80x9cThe CORDIC Trigonometric Computing Techniquexe2x80x9d, authored by Jack E. Volder, and published in IRE Trans. Electron. Comput. EC-8:330-334 (1959), Volder describes the Coordinate Rotation Digital Computer (CORDIC). In this article, which is incorporated by reference in its entirety, Volder discloses a computational algorithm based on a convergent series of elementary rotations. This algorithm will be referred to herein as the CORDIC algorithm. The CORDIC algorithm in its various realizations may be used to compute a variety of elementary functions such as, e.g., sine, cosine, tangent, arctangent, exponential, logarithm, hyperbolic sine, hyperbolic cosine, hyperbolic tangent, etc. In addition, the CORDIC algorithm may also be used to compute two-dimensional rotations, multiplications, divisions and square roots.
The CORDIC algorithm receives an input point (X0, Y0) and an input angle xcex0, and applies a series of iterations to these input operands. Each iteration of the series operates on a current intermediate point (Xi, Yi) and a current residual angle xcexi, and generates an updated intermediate point (Xi+1, Yi+1) and an updated residual angle xcexi+1. In the first iteration, the current intermediate point is taken to be the input point (X0, Y0) and the current residual angle is taken to be the input angle xcex0. A mathematical analysis of the CORDIC algorithm reveals that the intermediate point (Xi, Yi) converges as the iteration index increases. The limiting resultant point is given by the equations
                              X          R                =                              K            ⁢                          xe2x80x83                        ⁢                          R              0                        ⁢                          cos              ⁡                              (                                                      θ                    0                                    +                                      λ                    0                                                  )                                              =                                    lim                              i                →                ∞                                      ⁢                          X              i                                                          (        1        )                                                      Y            R                    =                                    K              ⁢                              xe2x80x83                            ⁢                              R                0                            ⁢                              sin                ⁡                                  (                                                            θ                      0                                        +                                          λ                      0                                                        )                                                      =                                          lim                                  i                  →                  ∞                                            ⁢                              Y                i                                                    ,                            (        2        )            
where K is a known constant, R0 is the radius of the point (X0, Y0) with respect to the origin, and xcex80 is the counter-clockwise angle of the input point (X0, Y0) with respect to the positive x axis. Geometrically, the resultant point (XR, YR) is a rotated and scaled image of the input point (X0, Y0). In other words, the resultant point (XR, YR) is that point which arises from rotating the input point (X0, Y0) by input angle xcex0 and then radially extending the interim rotated point by factor K. One advantage of the CORDIC algorithm lies in the fact that it implements this scaled rotation more efficiently than a direct computation of equations (1) and (2) which would generally require a pair of hardware multiplies and trigonometric evaluations.
Suppose that the input point (X0, Y0) is chosen to be (1/K,0). In this case, the initial radius R0 equals 1/K and the angle xcex80 of the input point with respect to the positive x axis equals zero. According to equations (1) and (2), after N iterations of the CORDIC algorithm, the x-coordinate XN approximates the value cos(xcex0), and the y-coordinate YN approximates the value sin(xcex0). By various arrangements of the initial conditions and the structure of the CORDIC algorithm, a great variety of elementary functions may be evaluated.
The CORDIC algorithm operates on the input point (X0, Y0) and the input angle xcex0 by applying an iterative series of pseudo-rotations governed by the following system of equations:
Yi+1=Yi+"xgr"i2xe2x88x92iXixe2x80x83xe2x80x83(3)
Xi+1=Xixe2x88x92"xgr"i2xe2x88x92iYixe2x80x83xe2x80x83(4)
xe2x80x83xcexi+1=xcexixe2x88x92"xgr"ixc2x7xcex1i,xe2x80x83xe2x80x83(5)
xcex1i=arctan(2xe2x88x92i),xe2x80x83xe2x80x83(6)
where the iteration index i is greater than or equal to zero, and where the scalar factor "xgr"i takes the value xc2x11 depending on the sign of the residual angle xcexi. In particular, if the residual angle xcexi is positive, the factor "xgr"i takes the value +1, and thus, equations (6) and (7) implement a pseudo-rotation of the intermediate point (Xi, Yi) by the angle xcex1i, and equation (8) computes an updated residual angle xcexi+1 by subtracting the angle xcex1i from the current residual xcexi. Conversely, if the residual angle xcexi is negative, the factor "xgr"i takes the value xe2x88x921, and thus, equations (6) and (7) implement a pseudo-rotation of the intermediate point (Xi, Yi) by the angle xe2x88x92xcex1i, and equation (8) computes the updated residual by adding the angle xcex1i to the current residual.
It is noted that equations (6) and (7) implement a pseudo-rotation of the point (Xi, Yi) by the rotation angle xcex1i. The direction of the pseudo-rotation (clockwise or counter-clockwise) depends on the value of factor "xgr"i. The resultant point (Xi+1, Yi+1) may be equivalently expressed by the relations
Yi+1={square root over (1+2xe2x88x922i+L )}Ri sin(xcex8i+"xgr"ixcex1i),xe2x80x83xe2x80x83(7)
Xi+1={square root over (1+2xe2x88x922i+L )}Ri cos(xcex8i+"xgr"ixcex1i),xe2x80x83xe2x80x83(8)
where Ri is the radius of the point (Xi, Yi), and xcex8i is the angle of the point (Xi, Yi) with respect to the positive x axis, i.e.
Yi=Ri sin(xcex8i),xe2x80x83xe2x80x83(9)
Xi=Ri cos(xcex8i).xe2x80x83xe2x80x83(10)
The resultant point (Xi+1, Yi+1) is slightly farther from the origin than the source point (Xi, Yi), i.e. by a factor of {square root over (1+2xe2x88x922i+L )}, and for this reason the resultant point cannot be said to be a pure rotation of the source point. 
As the iteration index i increases, the intermediate point (Xi, Yi) converges to the limiting resultant point given by equations (1) and (2). Furthermore, the residual angle xcexi converges to zero. It can be shown that the CORDIC algorithm exhibits an exponential rate of convergence, i.e. after N iterations of the CORDIC algorithm the residual angle xcexN has an absolute value smaller than 2xe2x88x92(Nxe2x88x921). In addition, the coordinates of the intermediate point (XN, YN) approximate the corresponding coordinates of the limiting resultant (XR, YR) to within a tolerance of KR02xe2x88x92(Nxe2x88x921). In other words, each iteration of the CORDIC algorithm yields an additional bit of precision in the binary representations of XN and YN.
Iteration equations (6), (7) and (8) may be efficiently implemented with (a) shifters configured to perform the indicated multiplications by powers of two, (b) adders configured to perform the addition and subtraction operations, and (c) a comparator to test the residual value for controlling the conditional additions and subtractions. In particular, it is noted that the iteration equations (6), (7) and (8) may be evaluated without performing hardware multiplies or trigonometric evaluations. The angular constants xcex1i may be stored in a lookup table. These features allow the CORDIC algorithm to compute approximations to XR and YR in significantly less time than direct implementations of equations (1) and (2) which achieve a comparable precision.
It is noted that multiplication of a binary number by xc2xd corresponds to shifting the bits of the binary number to the right one position with respect the binary point. In general, multiplication of a binary number by the factor 2xe2x88x92L corresponds to shifting the bits of the binary number to the right L bit positions.
Various ways to improve the CORDIC algorithm have been sought. One prior art method for improving the CORDIC algorithm has been advanced by Timmermann et al. in a paper entitled xe2x80x9cModified CORDIC Algorithm with Reduced Iterationsxe2x80x9d, Electronic Letters, vol. 25, no.15, pages 950-951, copyright 1989, which is hereby incorporated by reference in its entirety. Timmermann et al. make the observation that the first iterations of the CORDIC algorithm make the most significant contributions since the rotation angles xcex1i decrease with increasing iteration index i. The last iterations each contribute one additional bit of precision to the resultant values. Thus, an initial number J of CORDIC iterations may be performed, and the remaining number (N+1xe2x88x92J) of CORDIC iterations which would normally be required to achieve N bits of precision may be replaced by a single rotation step. If the number J is appropriately chosen the residual angle xcexJ will be sufficiently close to zero so that
|cos(xcexJ)xe2x88x921| less than 2xe2x88x92N.xe2x80x83xe2x80x83(11)
In particular, it can be shown that inequality (11) will be satisfied if   J   greater than                     N        +        1            2        .  
For example, integer J may be set equal to the smallest integer greater than or equal to             N      +      1        2    .
The intermediate point (XJ, YJ) resulting from the Jth CORDIC iteration may be rotated through the residual angle xcexJ using the relations
YT=xcexJXJ+Yj,xe2x80x83xe2x80x83(12)
XT=XJxe2x88x92xcexJYJ,xe2x80x83xe2x80x83(13)
where the sine and cosine of xcexJ are replaced by xcexJ and 1 respectively. The output point (XT, YT) approximates the point given by (KJR0 cos(xcex80+xcex0), KJR0 sin(xcex80+xcex0)) with N bits of precision, where
KJ={square root over (1+2xe2x88x922(0)+L )}{square root over (1+2xe2x88x922(1)+L )} . . . {square root over (1+2xe2x88x922(Jxe2x88x921)+L )}.xe2x80x83xe2x80x83(14)
If the rotation step given by equations (12) and (13) are implemented with a latency smaller than the latency of (N+1xe2x88x92J) CORDIC stages, the rotation step may advantageously replace computation of the last (N+1xe2x88x92J) CORDIC stages of the standard CORDIC algorithm. This procedure of performing J CORDIC iterations, where       J     greater than                   N        +        1            2        ,
followed by the rotation step of equations (12) and (13) will be referred to herein as the Timmermann algorithm.
The CORDIC algorithm and the Timmermann algorithm have gained a wide field of application due to their computational efficiency. Thus, any improvements to the CORDIC algorithm, especially improvements which exceed the speed and performance of the Timmermann algorithm, are highly desirable.
The present invention comprises a system and method for evaluating one or more functions using a succession of CORDIC stages/iterations followed by a rotation operation. The method of the present invention includes (a) accessing a first point from a first memory location, (b) accessing a first angle value from a second memory location, (c) applying the succession of CORDIC iterations to the first point and the first angle value in order to generate an output point and an output angle value, and (d) performing a rotation operation on the output point and the output angle value in order to generate a first resultant value and/or a second resultant value. The rotation operation includes
(1) determining the cosine of the output angle value and multiplying the cosine by a first coordinate of the output point to generate a first product;
(2) multiplying the output angle value by a second coordinate of the output point to generate a second product,
(3) subtracting [adding] the second product from the first product to generate the first resultant value;
(4) multiplying the cosine by the second coordinate of the output point to generate a third product,
(5) multiplying the output angle value by the first coordinate of the output point to generate a fourth product, and
(6) adding [subtracting] the third product and the fourth product to generate a second resultant value.
The first resultant value may represent the evaluation of a predetermined function on the first angle as an argument. The predetermined function may be a trigonometric function, an inverse trigonometric function, a hyperbolic function, an exponential function, a logarithmic function, etc. In addition, the first resultant value represents the evaluation of a predetermined function acting on the first point as an argument, i.e. a function of two variables. In one embodiment, the first resultant value and second resultant value may define coordinates of a resultant point which corresponds to an image of the first point rotated by the first angle value.
The number of CORDIC iterations in the succession is greater than or equal to (N+1)/3, wherein 2xe2x88x92N is a desired upper bound for the magnitude of the output angle value generated by the succession of CORDIC iterations. In equivalent terms, the integer N is the bit precision of the first resultant value.
The method of the present invention may be implemented by a software program executing on a microprocessor, or by a embedded microcode routine invoked from a microcode ROM within a microprocessor. The succession of CORDIC iterations may be executed in an iterative fashion using a single-stage CORDIC hardware execution unit. Alternatively, the succession of CORDIC iterations may be implemented in an unfolded CORDIC hardware unit comprising a plurality of stage, i.e. one stage per CORDIC iterations. In the preferred embodiment of the unfolded CORDIC hardware unit, the output angle value is generated significantly earlier than the output point giving a cosine unit computational headroom to compute the cosine of the output angle before the output point is generated.
The present invention also contemplates a system for performing a two-dimensional rotation using a succession of CORDIC stages and a completion unit. A first CORDIC stage of the succession receives a two-dimensional input point and an input angle (i.e. rotation angle). A last CORDIC stage of the succession generates an output point and an output angle value. The completion unit is coupled to the last CORDIC stage, and is configured to rotate the output point by the output angle and to thereby generate a rotated two-dimensional point. The completion unit comprises:
(1) a cosine unit configured to compute a cosine of the output angle value;
(2) a first multiplication unit configured to multiply the cosine value by a first coordinate of the output point to generate a first product;
(3) a second multiplication unit configured to multiply the output angle value by a second coordinate of the output point to generate a second product;
(4) an addition unit coupled to receive the first product and second product, and configured to add the second product to the first product to generate the first resultant value;
(5) a third multiplication unit configured to multiply the cosine value by the second coordinate in order to generate a third product;
(6) a fourth multiplication unit configured to multiply the output angle by the first coordinate in order to generate a fourth product; and
(7) a second addition unit configured to sum the third product and the fourth product in order to generate a second component of the rotated two-dimensional point.
The number of CORDIC stages in the succession is greater than or equal to (N+1)/3, where 2xe2x88x92N is a desired upper bound on the magnitude of the output angle generated by the succession of CORDIC stages. Equivalently, the integer N is a bit precision of a first component of the rotated two-dimensional point.
In the preferred embodiment of the rotation system the succession of CORDIC stages comprise an unfolded hardware structure. The succession of CORDIC stages may be partitioned into an X/Y path and a Z path. The X/Y path is configured to receive the two-dimensional input point and to generate the output point, and the Z path is configured to receive the rotation angle and generate the output angle. The Z path generates the output angle significantly earlier than X/Y path generates the output point. The Z cells comprising the Z path have significantly smaller propagation times than the X/Y cells comprising the X/Y path. Thus, the cosine unit is afforded time to compute the cosine of the output angle before the X/Y path generates the output point.